\chapter{Algorytm świetlika}
\thispagestyle{fancy}
  \section{Opis algorytmu}
  
Algorytm świetlika jest to metaheurystyczny algorytm optymalizacyjny, który powstał dzięki obserwacji zachowania świetlików. Każdy osobnik cechuje się pewną atrakcyjnością która decyduje o kierunku poruszania się pozostałych. Jeśli mamy dwa świetliki to ten który ma mniejszą atrakcyjność (słabiej świeci) będzie się przybliżał do drugiego z nich. Jednak atrakcyjność zależy nie tylko od jasności świecenia, ale również od odległości. Wraz ze zwiększaniem odległości maleje. Dodatkowo w związku z tym iż  jest to algorytm heurystyczny zawiera pewne elementy losowe. Jeśli świetlik nie ma w pobliżu sąsiada o większej atrakcyjności to może wykonać ruch niezależny od otoczenia.

  \section{Zasada działania}

\begin{enumerate}
\item Na początku definiujemy funkcję celu czyli problem który będziemy rozwiązywać, zadaniem algorytmu jest minimalizacja tej funkcji.
\item Generowana jest populacja początkowa jako pewne losowe rozmieszczenie świetlików.
\item Obliczana jest intensywność świecenia na podstawie funkcji celu, jeśli minimalizujemy funkcję celu to intensywność świecenia może być jej odwrotnością, czyli im lepsze rozwiązanie reprezentuje dany świetlik tym mocniej świeci.
\item Musimy jeszcze zdefiniować współczynnik absorpcji światła, jest to parametr określający zależność spadku atrakcyjności wraz z odległością.
\item Teraz w pętli wykonywane są kolejne iteracje algorytmu.
\item Każdego śwtetlika ($i$) po kolei porównujemy z pozostałymi ($j$) i, jeśli któryś świeci intensywniej, przesuwamy $i$ w stronę $j$.
\item Wektor przemieszczenia świetlika wylicza się z odpowiedniego wzoru uwzględniającego zarówno atrkcyjność w funkcji odległości jak i czynnik losowy.
\item Gdy zakończymy już porównywanie wszystkich świetlików i ich ruchy, wykonujemy losowy ruch świetlika, który był oceniony jako najlepszy na początku iteracji.
\item Wyznaczamy dla wszystkich świetlików wartość funkcji celu (w nowym położeniu) i na jej podstawie intersywność świecenia. szukamy najlepszego z nich (tego który najmocniej świeci), to on w tym momencie zawiera najlepsze rozwiązanie.
\item Redukujemy wartość współczynnika losowości zgodnie z przyjętym algorytmem i parametrem (opcjonalne).
\item Wykonywana jest kolejna iteracja.
\end{enumerate}

  \section{Dyskretny wersja algorytmu dostosowana do problemu flowshop}
  
Jak już wcześniej zostało napisane algorytm świetlika sam w sobie jest algorytmem metaheurystycznym. To znaczy że jest on pewnym szablonem algorytmu obliczającego przybliżone rozwiązanie danego problemu. Należy w tym celu odpowiednio przekształcić funkcję celu do zadania które rozwiązujemy i dostosować świetliki do przechowywania struktury rozwiązania. Trochę inaczej wygląda to w przypadku kiedy mamy do czynienia z problemem dyskretnym. Zauważmy że kiedy dla danego osobnika obliczamy ruch to w wyniku otrzymujemy pewną liczbę rzeczywistą, która w problemie dyskretnym nie może być zastosowana bezpośrednio. 

W naszym programie zaimplementowaliśmy rozwiązanie które przedstawili Mohammad Kazem Sayadi, Raza Ramezanianand i Nader Ghaffari Nasab. Opisali oni w swoim artykule w jaki sposób reprezentować świetliki oraz jak wyliczać nowe pozycje.
Jak wiadomo problem flowshop polega na uszeregowaniu n zadań w odpowiedniej kolejności tak aby zminimalizować rozpiętość czasową ich wykonania na m maszynach. Dodatkowym warunkiem jest to że zadanie w tym samym czasie może się wykonywać tylko na jednej maszynie.

Z racji tego, że świetliki muszą się znaleźć i przemieszczać po przestrzeni euklidesowej, istotą dyskretyzacji algorytmu jest znalezienie takiej przestrzeni i odpowiednie zmapowanie permutacji na taką przestrzeń. Sposób wygląda tak ($n$ oznacza ilość zadań). Świetliki umieszczamy w $n^2$-wymiarowej przestrzeni. $X_i$– wektor położenia $i$-tego świetlika.
$$X_i = [x_{i,1,1}, \ldots, x_{i,1,n}, \ldots, x_{i,n,1}, \ldots, x_{i,n,n}]$$
gdzie:
$$X_{i,j,k} = \left\{
\begin{array}{ll}
0 & \textrm{gdy }j\textrm{-te zadanie nie jest }k\textrm{-tym elementem permutacji} \\
1 & \textrm{gdy }j\textrm{-te zadanie jest }k\textrm{-tym elementem permutacji}
\end{array} \right.$$

Na początku każdej iteracji dla każdego świetlika jest formowany taki wektor zawierający $n$ jedynek i $n^2 - n$ zer (nie może być inaczej ponieważ każde z zadań może być tylko na jednej pozycji w permutacji). Mając tak dane świetliki możemy łatwo dokonywać zmian pozycji. Po porównaniu każdy z każdym składowe wektorów będą liczbami rzeczywistywi zawierającymi zarówno część całkowitą jak i ułamkową. Z racji tego, że należy z nich zbudować nową permutację, trzeba je przekształcić. Idea polega tym żeby te liczby przeskalowac na przedział $[0;1]$ dzięki czemu otrzymamy prawdopodobieństwa tego że w danej komórce może się znaleźć wartość jeden, tzn. że dane zadanie będzie miało właśnie taki numer porządkowy. To prawdopodobieństowo wyliczamy ze wzoru:
$$S(x_{i,j,k}) = \frac{1}{1+\exp(-x_{i,j,k})}$$
żeby miały wartość z przedziału $[0,1]$. Następnie czyścimy tablicę permutacji i dla każdego zadania robimy:
\begin{itemize}
\item Spośród $S(x_{i,j,1})\ldots S(x_{i,j,n})$ znajdujemy składową $S(x_{i,j,k})$ o największej wartości (a więc o największym priorytecie)
\item Sprawdzamy, czy $k$-te miejsce w permutacji jest już zajęte
\begin{itemize}
 \item Jeśli tak -- ignorujemy tę składową i poszukmy kolejnej największej (w razie potrzeby wykonywane aż do skutku)
 \item Jeśli nie -- zajmujemy tę pozycję tj. umieszczamy $j$-te zadanie na $k$-tej pozycji w permutacji
\end{itemize}
\end{itemize}
W ten sposób mamy nową permutację. Robiąc tak dla każdego świetlika, dostajemy zestaw nowych permutacji, prawdopodobnie bliższych optymalnej.


  \section{Parametry możliwe do ustawienia}
  
W programie można ustawiać następujące parametry (w nawiasie wartości domyślne):

\begin{itemize}
\item $\gamma$ $(1.0)$ - współczynnik absorpcji światła, reguluje zależność atrakcyjności od odległości, czyli jak bardzo maleje atrakcyjność danego świetlika wraz ze wzrostem jego odległości od obserwatora
\item $\alpha$ $(2.0)$ - stopień losowości, czynnik odpowiedzialny za to jak duży wpływ na ruch świetlika ma wartość losowa
\item $\alpha_{0}$ $(1.0)$ - parametr ograniczania losowości, z przedziału $[0;1]$, ma wpływ na to jak szybko maleje współczynnik losowości z każdą iteracją, im bliżej $1$ tym szybciej maleje $\alpha$ 
\item $\beta_{0}$  $(10.0)$ - bazowa atrakcyjność, pewna stała wartość która wpływa na wartość $\beta$
\item $\beta_{min}$  $(0.1)$ - minimalna atrakcyjność, dodatkowy parametr uwzględniony we wzorze na $\beta$, zalecany przy przestrzeniach wielowymiarowych
\item $m$ $(2.0)$ - wartość wykładnika potęgi do której podnosimy wartość odległości we wzorze na $\beta$ 
\item $n$ $(30)$ - ilość świetlików
\item $k$ $1000$ - ilość iteracji
\end{itemize}

  \section{Opis implementacji}
  \subsection{Pola}
Klasa Firefly reprezentuje model świetlika. Zawiera ona następujące pola:
\begin{itemize}
  \item tablica permutation w której pod kolejnymi indeksami są zapisane numery zadań występujące na tej pozycji w permutacji
  \item tablica dwuwymiarowa position, w wierszach są zadania natomiast w koumnach pozycje, jeśli zadanie występuje na danej pozycji w permutacji to w komórce jest wartość $1$, w przeciwnym wypadku $0$
  \item tablica occupation, pomocnicza tablica typu boolean ideksująca zadania, wartość true oznacza że zadanie ma już przypisaną pozycję
  \item pole time, obliczony sumaryczny czas dla aktualnej permutacji 
\end{itemize}



\subsection{Kolejne kroki algorytmu} 
\begin{enumerate}
\item Dla każdego świetlika w konstruktorze losowana jest pewna permutacja startowa i obliczany jest czas za pomocą zewnętrznej klasy SolutionEvaluator. Natępnie jest wywołana funcja findBest która zwraca numer najlepszego świetlika.
\item Zaczynają się kolejne iteracje. Na początku aktualizowana jest tablica position wartościami binarnymi na podstawie permutacji.
\item Teraz świetliki są sortowane malejąco według czasów (od najgorszego do najlepszego).
\item W tym momencie porównujemy wszystkie świetliki parami i wykonujemy ruch w stronę tego który mocniej świeci. 
Przesunięcie oznacza wywolanie funkcji moveTowards.
\item W funkcji moveTowards najpierw obliczana jest odległość między dwoma świetlikami. Pozycje są przechowywane w dwuwymiarowych tablicach wartościowanych $\left\lbrace 0,1\right\rbrace $ więc iterujemy po wierszach i kolumnach wykonując za każdym razem \\
$$distance += (position[i][j]-neighbour.position[i][j])^{2}$$
Łatwo zauważyć, że skoro 
$$position[i][j]-neighbour.position[i][j]$$
daje wynik 0, 1 albo -1, możemy uprościć obliczanie odległości do
$$distance += |position[i][j]-neighbour.position[i][j]|$$
Mając obliczoną odległość można wyliczyć wartość $\beta$, korzystamy tutaj z zależności \\
$$\beta = (\beta_{0}-\beta_{min})*e^{-\gamma * distance^{exponent}} + \beta_{min}$$
Teraz świetlik który wykonuje ruch musi zaktualizować swoją pozycję.\\
$$position[i][j] = position[i][j]*(1-\beta ) + (neighbour.position[i][j]*\beta) + \alpha *(random - 0.5)$$
\item Świetlik który był najlepszy na początku iteracji wykonuje ruch losowy\\
$$position[j][k] += (random - 0.5)*\alpha $$
\item Teraz dla każdego świetlika trzeba wygenerować nową permutację. Wywoływana jest funkcja applyNewPermutation. 
Najpierw obliczane jest prawdopodobieństwo (warotść z przedziału $[0;1])$\\
$$position[i][j] = \frac{1}{1 + e^{-position[i][j]}}$$
Następnie wyznaczamy nową permutację korzystając z prawdopodobieńst. Im większe prawdopodobieństwo tym większa szansa że dane zadanie znajdzie się na tej pozycji.
Jeśli jednak pozycja z największym prawdopodobieństwem jest już zajęta to rozpoczynamy poszukiwanie w pozostałych gdzie również szukamy największego prawdopodobieństwa. Na koniec mamy już wyliczone nowe permutacje.
\item Obliczane są nowe czasy dla każdego świetlika. I wyszukiwany jest najlepszy.
\item Dla najlepszego świetlika wykonujemy pewną optymalizację. Wywoływana jest funkcja localSearch. W tej funkcji sprawdzamy czy zamiana kolejności dwóch sąsiednich zadań nie zmniejszy nam czasu. Jeśli tak to dokonujemy zamiany.
\item Na końcu zwracamy wynik iteracji (tzn. najlepszy czas i permutację). A następnie zmniejszamy współczynnik $\alpha $ według wzorów \\
$$\delta = 1 - (\frac{10^{-4}}{0.9})^{\frac{1}{iterations}} $$ \\
$$\alpha *= 1 - \alpha_{0} * \delta $$
I wykonywana jest kolejna iteracja.
\end{enumerate}

  \section{Wyniki testów}
Porównaliśmy wyniki otrzymane przy pomocy algorytmu świetlika z najlepszymi znanymi rozwiązaniami. Do testów użyliśmy przykładowych instancji Tailarda. Poniższa tabela przedstawia te wyniki dla parametrów domyślnych.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline Ilość zadań & Ilość maszyn & Śr. z 5 testów & Wynik najlepszy \\ 
\hline 	20	&	5	&	1306,4	& 1232	\\ 
\hline 	20	&	5	&	1234,8	& 1180	\\ 
\hline 	20	&	5	&	1143,6	& 1082  \\ 
\hline 	20	&	10	&	1658,4	& 1448  \\ 
\hline 	20	&	10	&	1462,2	& 1290  \\ 
\hline 	20	&	10	&	1678	& 1356  \\
\hline 	20	&	20	&	2426,4	& 1911  \\  
\hline 	20	&	20	&	2367,6	& 1899  \\ 
\hline 	20	&	20	&	2270	& 1900  \\   
\hline 	50	&	5	&	2754,2	& 2712  \\
\hline 	50	&	5	&	2932,2	& 2837  \\ 
\hline 	50	&	5	&	2823,4	& 2776  \\
\hline 	50	&	10	&	3268,8	& 2907  \\
\hline 	50	&	10	&	3248,6	& 2941  \\
\hline 	50	&	10	&	3328,4	& 3046  \\
\hline 	50	&	20	&	4206,6	& 3480  \\
\hline 	50	&	20	&	4129,4	& 3460  \\
\hline 	50	&	20	&	4148,8	& 3438  \\
\hline 	100	&	5	&	5559	& 5437  \\
\hline 	100	&	10	&	6134,6	& 5759  \\
\hline 	100	&	20	&	6770	& 5851  \\
\hline 
\end{tabular} 
\end{center}

